"""
2561. 重排水果
困难
相关标签
premium lock icon
相关企业
提示
你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的交换成本。你想要让两个果篮相等。为此，可以根据需要多次执行下述操作：

选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
交换的成本是 min(basket1i,basket2j) 。
根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。



示例 1：

输入：basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出：1
解释：交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果，交换的成本为 1 。此时，basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组，发现二者相等。
示例 2：

输入：basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出：-1
解释：可以证明无法使两个果篮相等。


提示：

basket1.length == bakste2.length
1 <= basket1.length <= 105
1 <= basket1i,basket2i <= 109
"""
from collections import defaultdict
from typing import List


class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        allDp = {}
        dp1 = {}
        for i in basket1:
            dp1[i] = dp1.get(i,0) + 1
            allDp[i] = allDp.get(i,0) + 1
        for i in basket2:
            allDp[i] = allDp.get(i,0) + 1
        #
        diffDp = {}
        diffCount = 0
        for i,j in allDp.items():
            if j%2==1:
                return -1
            #每个数字要移动的次数
            diff = abs(j//2 - dp1.get(i,0))
            diffDp[i] = diff
            diffCount += diff
        print(diffDp)
        times = diffCount//2
        ans = 0
        keys = list(diffDp.keys())
        keys.sort()
        minKey = keys[0] #最数字，可通过最小数字移动两次达到移动某两个元素
        for k in keys:
            if times<=0:
                break
            #改数字要移动的次数
            time = diffDp.get(k)
            if time<=0:
                continue
            if time<=times:
                ans += time * min(k,minKey * 2) #如果key很大，则移动最小数子
                times -= time
            else:
                ans += times * min(k, minKey * 2)
                times = 0
        return ans

    def minCost_res1(self, basket1: List[int], basket2: List[int]) -> int:
        cnt = defaultdict(int)
        for x, y in zip(basket1, basket2):
            cnt[x] += 1
            cnt[y] -= 1  # 交集元素互相抵消

        a, b = [], []
        for x, c in cnt.items():
            if c % 2:  # 奇数无法均分
                return -1
            # 剩余元素的一半放入 a 或者 b
            if c > 0:
                a.extend([x] * (c // 2))
            else:
                b.extend([x] * (-c // 2))

        a.sort()
        b.sort(reverse=True)
        mn = min(cnt)  # 中介

        return sum(min(x, y, mn * 2) for x, y in zip(a, b))

if __name__ == '__main__':
    a = 1
    print(bin(a)[2:])
    a = -1
    print(bin(a)[2:])
    # print(Solution().minCost([4,2,2,2],[1,4,1,2]))
    # print(Solution().minCost([4,4,4,4,3],[5,5,5,5,3]))
    # print(Solution().minCost([84,80,43,8,80,88,43,14,100,88],[32,32,42,68,68,100,42,84,14,8]))# 48